// synch.cc
//        Routines for synchronizing threads.  Three kinds of
//        synchronization routines are defined here: semaphores, locks
//           and condition variables (the implementation of the last two
//        are left to the reader).
//
// Any implementation of a synchronization routine needs some
// primitive atomic operation.  We assume Nachos is running on
// a uniprocessor, and thus atomicity can be provided by
// turning off interrupts.  While interrupts are disabled, no
// context switch can occur, and thus the current thread is guaranteed
// to hold the CPU throughout, until interrupts are reenabled.
//
// Because some of these routines might be called with interrupts
// already disabled (Semaphore::V for one), instead of turning
// on interrupts at the end of the atomic operation, we always simply
// re-set the interrupt state back to its original value (whether
// that be disabled or enabled).
//
// Copyright (c) 1992-1993 The Regents of the University of California.
// All rights reserved.  See copyright.h for copyright notice and limitation
// of liability and disclaimer of warranty provisions.

#include "copyright.h"
#include "synch.h"
#include "system.h"
#include "alarm.h"

extern Thread* currentThread;

//----------------------------------------------------------------------
// Semaphore::Semaphore
//         Initialize a semaphore, so that it can be used for synchronization.
//
//        "debugName" is an arbitrary name, useful for debugging.
//        "initialValue" is the initial value of the semaphore.
//----------------------------------------------------------------------

Semaphore::Semaphore(char* debugName, int initialValue) {
    name = debugName;
    value = initialValue;
    queue = new List;
}

//----------------------------------------------------------------------
// Semaphore::Semaphore
//         De-allocate semaphore, when no longer needed.  Assume no one
//        is still waiting on the semaphore!
//----------------------------------------------------------------------

Semaphore::~Semaphore() {
    delete queue;
}

//----------------------------------------------------------------------
// Semaphore::P
//         Wait until semaphore value > 0, then decrement.  Checking the
//        value and decrementing must be done atomically, so we
//        need to disable interrupts before checking the value.
//
//        Note that Thread::Sleep assumes that interrupts are disabled
//        when it is called.
//----------------------------------------------------------------------

void
Semaphore::P() {
    IntStatus oldLevel = interrupt->SetLevel(IntOff);   // disable interrupts

    while (value == 0) {                         // semaphore not available
        queue->Append((void *)currentThread);        // so go to sleep
        currentThread->Sleep();
    }
    value--;                                         // semaphore available,
    // consume its value
    DEBUG('t',"in the semaphore\n");
    (void) interrupt->SetLevel(oldLevel);        // re-enable interrupts
}

//Wrap Semaphore::P() with a descriptive function name.
#ifdef CHANGED
void
Semaphore::Wait() {
    P();
}
#endif //defined CHANGED

//----------------------------------------------------------------------
// Semaphore::V
//        Increment semaphore value, waking up a waiter if necessary.
//        As with P(), this operation must be atomic, so we need to disable
//        interrupts.  Scheduler::ReadyToRun() assumes that threads
//        are disabled when it is called.
//----------------------------------------------------------------------

void
Semaphore::V() {
    Thread *thread;
    IntStatus oldLevel = interrupt->SetLevel(IntOff);

    thread = (Thread *)queue->Remove();
    // make thread ready, consuming the V immediately
    if (thread != NULL) {
        scheduler->ReadyToRun(thread);
    }
    value++;
    (void) interrupt->SetLevel(oldLevel);
}

#ifdef CHANGED
//Wrap Semaphore::V() with a descriptive fucntion name.
void
Semaphore::Signal() {
    V();
}
#endif //defined CHANGED

//----------------------------------------------------------------------
// Lock::Lock
//      Create a new lock object.
//      "name" is the object name for debugging purposes.
//      "locked" is the current state of the lock (true means locked).
//      "owner" is the current owner of the lock (NULL if unlokced).
//      "queue" is the heap of threads currently waiting for the lock.
//----------------------------------------------------------------------
Lock::Lock(char* debugName) {
#ifdef CHANGED
    name = debugName;
    locked = false;
    owner = NULL;
    queue = new ThreadHeap();
#endif //defined CHANGED
}

//----------------------------------------------------------------------
// Lock::Lock
//      Free up the memory associated with a mutex lock.
//----------------------------------------------------------------------
Lock::~Lock() {
#ifdef CHANGED
    ASSERT(owner == NULL);
    delete queue;
#endif //defined CHANGED
}

//----------------------------------------------------------------------
// Lock::Acquire
//      Acquire a mutually exclusive lock.
//      If called twice by the same thread before a Release, will abort.
//----------------------------------------------------------------------
void
Lock::Acquire() {
#ifdef CHANGED
    IntStatus oldLevel = interrupt->SetLevel(IntOff);

    ASSERT(owner != currentThread);

    while (locked) {
        queue->push(currentThread);
        currentThread->Sleep();
    }
    locked = true;
    owner = currentThread;

    (void) interrupt->SetLevel(oldLevel);
#endif //defined CHANGED
}

//----------------------------------------------------------------------
// Lock::AcquireNoBlock
//      Acquire a mutually exclusive lock, but don't block.
//      If called twice by the same thread before a Release, will abort.
//
//      "wait" is how long to wait for the lock. 0 specifies return immediately
//          if the lock is unavailable.
//----------------------------------------------------------------------
#ifdef CHANGED
bool
Lock::AcquireNoBlock(int wait) {
    IntStatus oldLevel = interrupt->SetLevel(IntOff);
    int start = stats->totalTicks;

    ASSERT(owner != currentThread);

    while(locked && wait > 0) {
        queue->push(currentThread);
        Alarm::GoToSleepFor(wait - (stats->totalTicks - start));
        if(locked && stats->totalTicks - start < wait) {
            break;
        }
    }

    if(locked) {
        return false;
    }

    (void) interrupt->SetLevel(oldLevel);
    return true;
}
#endif //defined CHANGED

//----------------------------------------------------------------------
// Lock::Release
//      Release a mutually exclusive lock.
//      Will abort if lock is not currently owned by this thread.
//----------------------------------------------------------------------
void
Lock::Release() {
#ifdef CHANGED
    IntStatus oldLevel = interrupt->SetLevel(IntOff);

    ASSERT(locked || owner == currentThread);

    queue->readyOne();

    locked = false;
    owner = NULL;

    (void) interrupt->SetLevel(oldLevel);
#endif //defined CHANGED
}

//----------------------------------------------------------------------
// Lock::isHeldByCurrentThread
//      Returns true if the current thread owns the lock.
//----------------------------------------------------------------------
#ifdef CHANGED
bool
Lock::isHeldByCurrentThread() {
    return owner == currentThread;

}
#endif //defined CHANGED

//----------------------------------------------------------------------
// Condition::Condition
//      Allocate space for a new condition variable.
//----------------------------------------------------------------------
Condition::Condition(char* debugName) {
#ifdef CHANGED
    name = debugName;
    queue = new List();
#endif //defined CHANGED
}

//----------------------------------------------------------------------
// Condition::~Condition
//      De-allocate space for a condition variable.
//----------------------------------------------------------------------
Condition::~Condition() {
#ifdef CHANGED
    delete queue;
#endif //defined CHANGED
}

//----------------------------------------------------------------------
// Condition::Wait
//      Wait for another thread to signal this one.
//----------------------------------------------------------------------
void
Condition::Wait(Lock* conditionLock) {
#ifdef CHANGED
    IntStatus oldLevel = interrupt->SetLevel(IntOff);

    ASSERT(conditionLock->isHeldByCurrentThread());

    conditionLock->Release();
    queue->Append((void *)currentThread);
    currentThread->Sleep();
    conditionLock->Acquire();

    (void) interrupt->SetLevel(oldLevel);
#endif //defined CHANGED
}

//----------------------------------------------------------------------
// Condition::Signal
//      Signal a different thread waiting on this lock that it should be
//      released. If no threads are waiting on the condition lock,
//      the signal is lost.
//----------------------------------------------------------------------
void
Condition::Signal(Lock* conditionLock) {
#ifdef CHANGED
    Thread *thread = NULL;
    IntStatus oldLevel = interrupt->SetLevel(IntOff);

    ASSERT(conditionLock->isHeldByCurrentThread());

    thread = (Thread *)queue->Remove();
    if (thread != NULL) {
        scheduler->ReadyToRun(thread);
    }

    (void) interrupt->SetLevel(oldLevel);
#endif //defined CHANGED
}


//----------------------------------------------------------------------
// Condition::Signal
//      Signal all threads waiting on this lock that they should be
//      released. If no threads are waiting on the condition lock,
//      the signal is lost.
//----------------------------------------------------------------------
void
Condition::Broadcast(Lock* conditionLock) {
#ifdef CHANGED
    IntStatus oldLevel = interrupt->SetLevel(IntOff);

    ASSERT(conditionLock->isHeldByCurrentThread());

    while(!queue->IsEmpty()) {
        scheduler->ReadyToRun((Thread*)queue->Remove());
    }

    (void) interrupt->SetLevel(oldLevel);
#endif //defined CHANGED
}
